<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Nonnegative matrix factorization</title>
<link rel="canonical" href="/Users/mcgrant/Projects/CVX/examples/html/nonneg_matrix_fact.html">
<link rel="stylesheet" href="../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Nonnegative matrix factorization</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Argyris Zymnis, Joelle Skaf, Stephen Boyd</span>
<span class="comment">%</span>
<span class="comment">% We are given a matrix A in R^{m*n}</span>
<span class="comment">% and are interested in solving the problem:</span>
<span class="comment">%</span>
<span class="comment">% minimize    ||A - Y*X||_F</span>
<span class="comment">% subject to  Y &gt;= 0, X &gt;= 0</span>
<span class="comment">%</span>
<span class="comment">% where Y in R{m*k} and X in R{k*n}.</span>
<span class="comment">% This script generates a random matrix A and obtains an</span>
<span class="comment">% *approximate* solution to the above problem by first generating</span>
<span class="comment">% a random initial guess for Y and the alternatively minimizing</span>
<span class="comment">% over X and Y for a fixed number of iterations.</span>

<span class="comment">% Generate data matrix A</span>
rstate = rand(<span class="string">'state'</span>);
m = 10; n = 10; k = 5;
A = rand(m,k)*rand(k,n);

<span class="comment">% Initialize Y randomly</span>
Y = rand(m,k);

<span class="comment">% Perform alternating minimization</span>
MAX_ITERS = 30;
residual = zeros(1,MAX_ITERS);
<span class="keyword">for</span> iter = 1:MAX_ITERS
    cvx_begin <span class="string">quiet</span>
        <span class="keyword">if</span> mod(iter,2) == 1
            variable <span class="string">X(k,n)</span>
            X &gt;= 0;
        <span class="keyword">else</span>
            variable <span class="string">Y(m,k)</span>
            Y &gt;= 0;
        <span class="keyword">end</span>
        minimize(norm(A - Y*X,<span class="string">'fro'</span>));
    cvx_end
    fprintf(1,<span class="string">'Iteration %d, residual norm %g\n'</span>,iter,cvx_optval);
    residual(iter) = cvx_optval;
<span class="keyword">end</span>

<span class="comment">% Plot residuals</span>
plot(residual);
xlabel(<span class="string">'Iteration Number'</span>);
ylabel(<span class="string">'Residual Norm'</span>);

<span class="comment">% Display results</span>
disp( <span class="string">'Original matrix:'</span> );
disp( A );
disp( <span class="string">'Left factor Y:'</span> );
disp( Y );
disp( <span class="string">'Right factor X:'</span> );
disp( X );
disp( <span class="string">'Residual A - Y * X:'</span> );
disp( A - Y * X );
fprintf( <span class="string">'Residual after %d iterations: %g\n'</span>, iter, cvx_optval );
</pre>
<a id="output"></a>
<pre class="codeoutput">
Iteration 1, residual norm 2.26648
Iteration 2, residual norm 0.660781
Iteration 3, residual norm 0.44153
Iteration 4, residual norm 0.336907
Iteration 5, residual norm 0.239933
Iteration 6, residual norm 0.18738
Iteration 7, residual norm 0.154083
Iteration 8, residual norm 0.128125
Iteration 9, residual norm 0.10558
Iteration 10, residual norm 0.0872846
Iteration 11, residual norm 0.0730054
Iteration 12, residual norm 0.0623666
Iteration 13, residual norm 0.0546671
Iteration 14, residual norm 0.0488472
Iteration 15, residual norm 0.0440959
Iteration 16, residual norm 0.040119
Iteration 17, residual norm 0.0367989
Iteration 18, residual norm 0.0339624
Iteration 19, residual norm 0.0315186
Iteration 20, residual norm 0.0293616
Iteration 21, residual norm 0.0274349
Iteration 22, residual norm 0.0256886
Iteration 23, residual norm 0.0240904
Iteration 24, residual norm 0.0226158
Iteration 25, residual norm 0.021246
Iteration 26, residual norm 0.0199695
Iteration 27, residual norm 0.0187749
Iteration 28, residual norm 0.0176563
Iteration 29, residual norm 0.0166057
Iteration 30, residual norm 0.0156197
Original matrix:
  Columns 1 through 7

    0.7853    1.1043    0.5464    0.8821    0.9633    0.9120    0.8624
    1.6281    2.2127    1.1835    1.7593    1.9218    1.8189    1.6919
    0.9260    1.3156    0.6115    1.0933    1.2980    1.1348    1.1092
    1.1830    1.9762    1.1304    1.4130    1.4772    1.5964    1.1147
    1.2148    1.6831    0.9346    1.3715    1.5540    1.4853    1.2150
    0.7934    1.7606    0.8839    1.0301    1.1985    1.0598    1.1130
    1.0306    1.4870    0.6897    1.1861    1.4357    1.1857    1.2986
    0.9363    1.9364    0.9074    1.3523    1.5164    1.5405    1.1609
    1.0981    1.6368    0.8873    1.3303    1.5322    1.4920    1.1132
    1.0697    1.8210    1.0921    1.3177    1.5436    1.5176    1.0405

  Columns 8 through 10

    0.9490    0.4810    0.6907
    1.9100    1.1375    1.3869
    1.1896    0.7200    0.7121
    1.6666    1.1085    1.1592
    1.4924    1.1380    0.9382
    1.5280    0.7139    0.9701
    1.3526    0.7723    0.8165
    1.6706    0.8763    0.9997
    1.4644    1.1687    0.8353
    1.6373    1.4800    0.8682

Left factor Y:
   1.0e+03 *

    0.0012    0.0004    0.0002    0.0000    0.0006
    0.0023    0.0010    0.0005    0.4445    0.0008
    0.0018    0.0000    0.0003    0.8346    0.0011
    0.0000    0.0010    0.0007    0.0433    0.0001
    0.0014    0.0003    0.0006    1.0572    0.0005
    0.0001    0.0011    0.0000    1.8709    0.0009
    0.0022    0.0002    0.0002    1.5105    0.0013
    0.0000    0.0004    0.0004    0.0000    0.0013
    0.0010    0.0000    0.0007    1.0500    0.0007
    0.0001    0.0003    0.0008    2.5220    0.0002

Right factor X:
  Columns 1 through 7

    0.1985    0.0000    0.0102    0.1099    0.1233    0.0609    0.1704
    0.4760    0.8742    0.4933    0.5116    0.4927    0.5123    0.5156
    0.9951    1.4881    0.8889    1.2413    1.3420    1.4987    0.7934
    0.0000    0.0001    0.0001    0.0000    0.0001   -0.0000    0.0000
    0.2530    0.7519    0.2608    0.4876    0.5890    0.5468    0.4872

  Columns 8 through 10

    0.0096    0.0259    0.0648
    0.7050    0.2525    0.6075
    1.2956    1.2146    0.7529
    0.0001    0.0001    0.0000
    0.6603    0.2002    0.3440

Residual A - Y * X:
  Columns 1 through 7

    0.0011   -0.0005   -0.0015    0.0042   -0.0019    0.0095   -0.0059
   -0.0002   -0.0003    0.0000   -0.0003   -0.0001    0.0003    0.0002
   -0.0000   -0.0001    0.0000   -0.0000   -0.0000    0.0000    0.0000
   -0.0002   -0.0002   -0.0001   -0.0005   -0.0002    0.0005    0.0003
    0.0000   -0.0000    0.0000    0.0001    0.0000   -0.0001   -0.0001
    0.0001    0.0008   -0.0001    0.0004    0.0003   -0.0020    0.0005
    0.0001    0.0001    0.0001    0.0004    0.0001   -0.0004   -0.0003
   -0.0004    0.0000   -0.0001   -0.0007   -0.0005    0.0014   -0.0001
   -0.0000   -0.0000   -0.0000   -0.0000   -0.0000    0.0000    0.0000
    0.0004    0.0005    0.0001    0.0010    0.0003   -0.0010   -0.0007

  Columns 8 through 10

   -0.0037   -0.0074    0.0035
    0.0001    0.0001    0.0002
    0.0000    0.0000    0.0000
   -0.0000    0.0001    0.0003
    0.0001   -0.0000   -0.0000
    0.0004   -0.0009   -0.0004
    0.0001   -0.0001   -0.0002
   -0.0003   -0.0001    0.0006
   -0.0000    0.0000    0.0000
   -0.0001   -0.0003   -0.0006

Residual after 30 iterations: 0.0156197
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="nonneg_matrix_fact__01.png" alt=""> 
</div>
</div>
</body>
</html>